package com.njupt.DynamicProgramming;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/8 10:50
 * @Description: 377. 组合总和 Ⅳ
 * 法一、动态规划
 * 1、dp[j] 表示容量为j的背包 组合成j时的元素组合个数
 * 2、递推公式 dp[j] += dp[j-nums[i]]
 * 3、dp[0] = 1
 * @Version: 1.0
 */


public class CombinationSum4_377 {

    public int combinationSum4(int[] nums, int target) {

        //法一、动态规划法
        int[] dp = new int[target+1];
        dp[0] = 1;
        for (int i = 0; i <= target ; i++) { //先遍历背包
            for (int j = 0; j < nums.length; j++) {
                if(i >= nums[j]  && dp[i] + dp[i-nums[j]] < Integer.MAX_VALUE){
                    dp[i] += dp[i-nums[j]];
                }
            }
        }
        return dp[target];


        //2、回溯法



    }

    public static void main(String[] args) {
        CombinationSum4_377 test = new CombinationSum4_377();
        int[] nums = {1,2,3};
        System.out.println(test.combinationSum4(nums, 4));

    }
}
